We must move beyond Breadth-First Search (BFS) to handle graphs where edges have associated costs.

  • We already have an algorithm that finds shortest paths: Breadth-First Search (BFS).
  • BUT: BFS only works on unweighted graphs, where "shortest" means the fewest number of edges.
  • Let's trace BFS on our weighted graph (A to D).
  • BFS explores nodes layer by layer, finding the 2-edge path $A \to B \to D$ first.
  • This path has a total cost of $10 + 1 = 11$.
  • The true shortest path is $A \to C \to B \to D$, which has 3 edges but a total cost of $1 + 1 + 1 = 3$.
  • Problem: BFS finds the path with the fewest edges, not the lowest cost.
  • We need an algorithm that is "cost-aware" and prioritizes cheaper paths, regardless of edge count.
Algorithm Finds Shortest Path? Path Found (A to D) Why it Fails
BFS Only for unweighted A, B, D (2 edges) Ignores weights. Finds fewest edges, not lowest cost.
(Needed) Yes, for weighted A, C, B, D (cost 3) Must prioritize paths by total weight, not edge count.